## QuickSort R
import random
import time
import datetime

## generate random array[]
def GetRandomArray(arrayLength = 100, maxValue = 10000):
	randomArray = []
	for i in range (0, arrayLength):
		randomArray.append(random.randint(0, maxValue))
	return randomArray

def QuickSort(array, start, end):
	if (start >= end):
		return
	index = Partition(array, start, end)
	QuickSort(array, start, index - 1)
	QuickSort(array, index + 1, end)

def Partition(array, start, end):
	left = start
	right = end
	pivot = array[end]
	while(left < right):
		while (left < right and array[left] <= pivot):
			left += 1
		while (left < right and array[right] >= pivot):
			right -= 1
		array[left], array[right] = array[right], array[left]
	array[left], array[end] = array[end], array[left]
	return left

def CheckSort(array_old, array):
	errorFlag = 0
	for i in range (0, len(array) - 1):
		if (array[i] > array[i + 1]):
			print('Sort Error')
			print('#======================#')
			errorFlag = 1
			break
	if(len(set(array_old)) != len(set(array))):
		print('Sort Error!   Array has been changed.')
		print('#======================#')
		errorFlag = 1
	if not errorFlag:
		print('Sort succeed!')
		print('#======================#')
	return errorFlag

def MultiTest(testNumber):
	array = []
	array_old = []
	array = GetRandomArray(800000, 1000000)
	array_old = array.copy()

	print('Number %d test:' %(testNumber + 1))
	print('Sorting...')
	time_start = datetime.datetime.now()
	QuickSort(array, 0, len(array) - 1)
	time_stop = datetime.datetime.now()
	time_cost = (time_stop - time_start)
	errorFlag = CheckSort(array_old, array)
	if (1 == errorFlag):
		return testNumber
	print('Timecost: %s' %time_cost)
	print('#======================#')


if __name__ == '__main__':
	testNumber = 1
	error = []
	for i in range (testNumber):
		if (None != MultiTest(i)):
			error.append(i + 1)
	print('Error number:')
	print(error)
